// https://leetcode.cn/problems/text-justification/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
    string geneSpacing(int n) {
        string s = "";
        for (int i = 0; i < n; i++) s += ' ';
        return s;
    }

    string joinStr(vector<string>& words, int left, int right, int sep) {
        string s = "";
        for (int i = left; i < right; i++) {
            if (i == left) {
                s += words[left];
            } else {
                s += geneSpacing(sep);
                s += words[i];
            }
        }
        return s;
    }
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        int n = words.size();
        int right = 0;
        vector<string> ans;

        while (true) {
            int left = right;
            int sumLen = 0;

            while (right < n && sumLen + words[right].size() + right - left <= maxWidth) {
                sumLen += words[right].size();
                right++;
            }

            if (right == n) {
                string s = joinStr(words, left, n, 1);
                s += geneSpacing(maxWidth - s.size());
                ans.push_back(s);
                break;
            }

            int wordsCount = right - left;
            int spacingCount = maxWidth - sumLen;

            if (wordsCount == 1) {
                string s = words[left] + geneSpacing(spacingCount);
                ans.push_back(s);
                continue;
            }

            int avgSpacing = spacingCount / (wordsCount - 1);
            int extraSpacing = spacingCount % (wordsCount - 1);
            string s1 = joinStr(words, left, left + extraSpacing + 1, avgSpacing + 1);
            string s2 = joinStr(words, left + extraSpacing + 1, right, avgSpacing);
            string s3 = s1 + geneSpacing(avgSpacing) + s2;
            ans.push_back(s3);
        }
        return ans;
    }
};